#pragma once
#include "../Math/Array.hpp"

namespace zzz{
template<typename T>
class SumTable
{
public:
  SumTable():ready_(false){}
  SumTable(const Array<2, T> &value)
  {
    Prepare(value);
  }

  void Prepare(const Array<2, T> &value)
  {
    table_.SetSize(value.Size());
    for (int r=0; r<table_.Size(0); r++) for (int c=0; c<table_.Size(1); c++)
    {
      T previous=0;
      if (r!=0) previous+=table_[Vector2ui(r-1, c)];
      if (c!=0) previous+=table_[Vector2ui(r, c-1)];
      if (c!=0 && r!=0) previous-=table_[Vector2ui(r-1, c-1)];
      table_[Vector2ui(r, c)]=previous+value[Vector2ui(r, c)]; 
    }
    ready_=true;
  }

  //bottomdown included and leftup included
  T GetSum(const Vector2ui &leftup, const Vector2ui &bottomdown)
  {
    ZCHECK(ready_);
    ZCHECK(bottomdown>=leftup && bottomdown<table_.Size());
    zuint beginr=leftup[0],beginc=leftup[1],endr=bottomdown[0],endc=bottomdown[1];
    T ret=table_[Vector2ui(endr,endc)];
    if (beginr>0) ret-=table_[Vector2ui(beginr-1,endc)];
    if (beginc>0) ret-=table_[Vector2ui(endr,beginc-1)];
    if (beginr>0 && beginc>0) ret+=table_[Vector2ui(beginr-1,beginc-1)];
    return ret;
  }

private:
  Array<2, T> table_;
  bool ready_;
};
}